#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from math import ceil, log


class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end


class Solution:
    """
    @param A: An integer array
    @param queries: An query list
    @return: The result list
    """
    SEG_MAX = 2 ** 32
    SPARSE_MAX = 2 ** 32

    def intervalMinNumber(self, A, queries):
        # return self.interval_min_number_seg_tree(A, queries)
        return self.sparse_table_min_number(A, queries)

    # =================== sparse table min =====================
    def sparse_table_min_number(self, A, queries):
        self.len = len(A)
        self.A = A
        self._build_min_sparse_table()

        ret = []
        for q in queries:
            ret.append( self._query_sparse(q.start, q.end) )

        return ret

    def _query_sparse(self, start, end):
        # assert end >= start
        query_len  = end - start + 1
        query_base = int( log(query_len, 2) )

        part2_min = self.SPARSE_MAX

        part1_min = self.sparse_table[start][query_base]
        new_start = end - 2**query_base + 1
        if new_start > start:
            part2_min = self.sparse_table[new_start][query_base]

        return min(part1_min, part2_min)

    def _build_min_sparse_table(self):
        self.base = int(log(self.len, 2)) + 1       # 虽然是向下取整, 但是(base + base)>整个长度: 两次查询, +1是因为range时不包括最后一位
        self.sparse_table = self._make_matrix(self.len, self.base)

        for start in range(self.len):
            # print(start)
            self.sparse_table[start][0] = self.A[start]

        for expo in range(1, self.base):
            for start in range(self.len):
                # (start + 2 ** expo - 1) > (self.len - 1) ===> belows inequality
                if start + 2 ** expo  > self.len:
                    break

                expo_off1 = expo-1
                part1_min = self.sparse_table[start][expo_off1]
                part2_min = self.sparse_table[start+ 2 ** expo_off1][expo_off1]
                self.sparse_table[start][expo] = min(part1_min, part2_min)

        from pprint import pprint
        # pprint(self.sparse_table)

    def _make_matrix(self, rows, cols, init_value=None):
        one_row = [init_value] * cols
        mat = [list(one_row) for row in range(rows)]
        return mat

    # =================== segment tree =====================
    def interval_min_number_seg_tree(self, A, queries):
        self.A = A
        self.len = len(A)
        self.build_seg_tree()

        ret = []

        # print(type(queries))
        for one_query in queries:
            ret.append( self.query(one_query.start, one_query.end) )

        return ret

    def query(self, qleft, qright):
        # [qleft, qright)
        return self._query_rec(qleft, qright+1, seg_left=0, seg_right=self.len, seg_pos=0)

    def _query_rec(self, qleft, qright, seg_left, seg_right, seg_pos):
        if seg_left >= qleft and seg_right <= qright:
            return self.seg_tree[seg_pos]

        if qleft >= seg_right or qright <= seg_left:
            return self.SEG_MAX

        mid = (seg_left + seg_right + 1) // 2
        left_min  = self._query_rec(qleft, qright, seg_left, mid, seg_pos*2+1)
        right_min = self._query_rec(qleft, qright, mid, seg_right, seg_pos*2+2)
        # print(left_min, right_min)
        return min(left_min, right_min)

    def build_seg_tree(self):
        # seg_size = 4 * self.len
        base_size = ceil(log(self.len, 2))      # 向最小的 2**n 对齐
        seg_size = 2 * (2 ** base_size) - 1
        self.seg_tree = [None] * seg_size

        self._build_rec(0, 0, self.len)
        print(self.seg_tree)


    def _build_rec(self, seg_pos, start, end):
        # [start, end) open-close interval
        # print(start, end)
        assert end > start
        if start + 1 == end:
            self.seg_tree[seg_pos] = self.A[start]
        else:
            mid = (start + end + 1) // 2
            left_min  = self._build_rec(seg_pos*2+1, start, mid)
            right_min = self._build_rec(seg_pos*2+2, mid, end)
            self.seg_tree[seg_pos] = min(left_min, right_min)

        return self.seg_tree[seg_pos]


def main():
    print("start main")
    s = Solution()
    ret = s.intervalMinNumber([1,-2,3,-4, 5, -6], [Interval(2, 2)])
    ret = s.intervalMinNumber([1,-2,3,-4, 5, -6], [Interval(1, 1)])
    ret = s.intervalMinNumber([1,-2,3,-4, 5, -6], [Interval(0, 0)])
    ret = s.intervalMinNumber([1,-2,3,-4, 5, -6], [Interval(2, 4)])
    # ret = s.intervalMinNumber([1,-2,3], [Interval(2, 2)])

    # s.intervalMinNumber([1, 2], None)
    # ret = s.query(0, 0)
    # ret = s.query(1, 1)
    # ret = s.query(1, 2)
    # ret = s.query(2, 2)
    # ret = s.query(0, 1)
    print(ret)

if __name__ == "__main__":
    main()
